package practice_2025_6_30;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 双指针练习
 */
public class Solution {

    /**
     * 移动零
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        for(int left = 0, right = 0; right < len; right++) {
            if (nums[right] != 0) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
            }
        }
    }

    /**
     * 复写0
     * @param arr
     */
    public void duplicateZeros(int[] arr) {
        // 找到需要复写的最后一个元素
        int slow = 0, fast = 0;
        int len = arr.length;
        while(fast < len - 1) {
            if (arr[slow] == 0) {fast++;}
            slow++;
            fast++;
        }
        System.out.println(slow);
        System.out.println(fast);
        // 从后向前进行复写(slow 为最后一个要复写的元素)
        // 若最后一位是0，0可能复写1次或两次，需要先特殊处理
        if (fast == len - 1 && arr[slow] == 0) {
            arr[len - 1] = 0;
            slow--;
            fast = len - 2;
        }
        if (fast == len) {
            slow--;
            fast--;
        }

        while(slow >= 0) {
            if (arr[slow] != 0) {
                arr[fast--] = arr[slow--];
            } else {
                arr[fast--] = 0;
                arr[fast--] = 0;
                slow--;
            }
        }
    }

    /**
     * 快乐数
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        int slow = n, fast = sumOfSquares(n);
        while(slow != fast) {
            slow = sumOfSquares(slow);
            fast = sumOfSquares(sumOfSquares(fast));
        }
        // System.out.println(slow);
        return slow == 1;
    }

    public int sumOfSquares(int n) {
        int sum = 0;
        while(n > 0) {
            int k = n % 10;
            sum += k * k;
            n /= 10;
        }
        return sum;
    }

    /**
     * 有效三角形的个数
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        // 固定一个数，然后剩下的使用双指针寻找
        int sum = 0;
        int len = nums.length;
        Arrays.sort(nums);
        for(int i = len - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while(left < right) {
                // 无效三角形
                if (nums[left] + nums[right] <= nums[i]) {
                    left++;
                } else {
                    // 有效三角形
                    //     System.out.println(right - left);
                    sum += (right - left);
                    right--;
                }
            }
        }
        return sum;
    }

    /**
     * 四数之和
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 先对数组进行排序
        Arrays.sort(nums);
        int i = len - 1;
        while(i >= 3) {
            int j = i - 1;
            while(j >= 2) {
                long t = (long)target - nums[i] - nums[j];
                int left = 0, right = j - 1;
                while(left < right) {
                    if (nums[left] + nums[right] < t) {
                        left++;
                    } else if (nums[left] + nums[right] > t) {
                        right--;
                    } else {
                        List<Integer> list = new ArrayList<>(Arrays.asList(nums[left], nums[right], nums[j], nums[i]));
                        res.add(list);
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left - 1]) {left++;}
                        while(left < right && nums[right] == nums[right + 1]) {right--;}
                    }
                }
                // 向前移动j
                j--;
                while(j >= 2 && nums[j]== nums[j + 1]) {
                    j--;
                }
            }
            // 向前移动 i
            i--;
            while(i >= 3 && nums[i] == nums[i + 1]) {
                i--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,2,2,2};
        fourSum(nums, 8);
    }
}
